// https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

// 算法思路总结：
// 1. 深度优先搜索统计可达格子数量
// 2. 数位和判断作为移动的约束条件
// 3. 从起点开始递归探索四个方向
// 4. 使用访问数组避免重复计数
// 5. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <cstring>
#include <algorithm>
#include <vector>

class Solution 
{
public:
    int m, n, cnt, ret;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    bool vis[101][101];

    int wardrobeFinishing(int _m, int _n, int _cnt) 
    {
        memset(vis, 0, sizeof(vis));
        ret = 0, m = _m, n = _n, cnt = _cnt;

        dfs(0, 0);

        return ret;
    }

    void dfs(int a, int b)
    {
        vis[a][b] = true;
        ret++;

        for (int i = 0 ; i < 4 ; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 0 && y >= 0 && x < m && y < n && vis[x][y] == false && digit(x) + digit(y) <= cnt)
            {
                dfs(x, y);
            }
        }
    }

    int digit(int num)
    {
        int sum = 0;
        while (num > 0)
        {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
};

int main()
{
    int m = 4, n = 7, cnt = 5;
    Solution sol;

    cout << sol.wardrobeFinishing(m, n, cnt) << endl;

    return 0;
}